﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SmartRoute.Randomness
{
    [Serializable]
    /// <summary>
    /// Maintains a System.Random object as internal state, offering
    /// high-level random functions using this object.
    /// Works deterministically against its seed, but the methods are
    /// not pure. Copy it in advance to ensure that it remains pure.
    /// </summary>
    public struct RandomSource
    {
        //TODO: Write tests.

        #region State fields

        /// <summary>
        /// The internal random number generator.
        /// </summary>
        private Random _prng;

        #endregion

        #region Construction & Branching

        /// <summary>
        /// Makes a new RandomSource object with a given random number generator.
        /// Do not expose this constructor! 
        /// Switching away from System.Random as the pseudorandom source should
        /// not break calling code!
        /// </summary>
        /// <param name="rng">The random number generator</param>
        private RandomSource(Random rng)
        {
            _prng = rng;
        }

        /// <summary>
        /// Makes a new RandomSource object with the given random seed.
        /// </summary>
        /// <param name="rng">The random seed that will initialize the pseudo-random number generator.</param>
        public RandomSource(int seed)
        {
            _prng = new Random(seed);
        }

        /// <summary>
        /// Branches another RandomSource state off of this one.
        /// </summary>
        public RandomSource branch()
        {
            return new RandomSource(_prng.Next());
        }

        #endregion

        #region Deterministic Operations

        /// <summary>
        /// Swaps two elements of an array destructively.
        /// </summary>
        /// <param name="array">The array to be modified.</param>
        /// <param name="index1">The index of the first element to be swapped.</param>
        /// <param name="index2">The index of the second element to be swapped.</param>
        private static void swap(object[] array, int index1, int index2)
        {
            object tmp;
            tmp = array[index1];
            array[index1] = array[index2];
            array[index2] = tmp;
        }

        /// <summary>
        /// An accumulating scan over an array of integers, returning intermediate sums.
        /// </summary>
        private static double[] SummingScan(double[] summands)
        {
            //Trivial case. Shallow copy is okay as ints are immutable
            if (summands.Length < 2) return (double[])summands.Clone();
            double[] summations = new double[summands.Length];
            summations[0] = summands[0];
            for (int i = 1; i < summations.Length; i++)
            {
                summations[i] = summations[i - 1] + summands[i];
            }
            return summations;
        }

        #endregion

        #region Simple Random Operations

        /// <summary>
        /// A fair coin flip.
        /// </summary>
        public bool coinflip()
        {
            //Check if the unit bit is 1. No bias here at all.
            return (_prng.Next() & 1) == 1;
        }

        /// <summary>
        /// Returns a random integer between the two given inclusive bounds.
        /// The first bound must be lower than the second.
        /// </summary>
        public int fromTo(int incLowerBound, int incUpperBound)
        {
            return _prng.Next(incLowerBound, incUpperBound + 1);
        }

        /// <summary>
        /// Returns indexes of where the ball stopped on the roullete wheel.
        /// </summary>
        private IEnumerable<int> roulleteWheelSpinner(double[] summations)
        {
            if (summations.Length < 1) throw new ArgumentException("roulette wheel must have at least one element");
            if (summations.Length == 1) for (; ; ) yield return 0; //Return 0 forever if there is only 1 element.
            
            //Look in square-root-of-length steps on summations
            int step = Convert.ToInt32(Math.Floor(Math.Sqrt(Convert.ToDouble(summations.Length))));

            //First step should set up so that the initial incrementation by square roots
            // does not call outside of array bounds
            int initialStep = (summations.Length - 1) % step;

            for(;;)
            {
                //Set the starting index at 0 or the needed offset to avoid out-of-bounds
                int index = initialStep;

                //Choose a random value between 0 and the total weight of the wheel
                double spin = _prng.NextDouble() * summations[summations.Length - 1];

                //Go in square-root increments until the total is larger than our spun value.
                for (; index < summations.Length - 1 && spin > summations[index]; index += step) ;

                //Lower the index until the spin is bigger than the preceeding value.
                for (; index > 0 && spin < summations[index - 1]; index--) ;

                //Output the index.
                yield return index;
            }
        }

        /// <summary>
        /// Choose a random number between the lower bound and an exclusive upper bound, IE for array indices.
        /// </summary>
        /// <param name="lowerBound">An inclusive lower bound.</param>
        /// <param name="exclusiveUpperBound">An exclusive upper bound.</param>
        /// <returns>A number ranging between the lower bound and the upper bound minus one.</returns>
        public int Next(int lowerBound, int exclusiveUpperBound)
        {
            return this._prng.Next(lowerBound, exclusiveUpperBound);
        }

        public int Next()
        {
            return this._prng.Next();
        }

        public double NextDouble()
        {
            return this._prng.NextDouble();
        }

        #endregion

        #region Permutations

        /// <summary>
        /// Destructively swaps two elements in an array at random.
        /// </summary>
        /// <param name="array">The array to be modified.</param>
        public void randomSwap(object[] array)
        {
            swap(array, _prng.Next(array.Length), _prng.Next(array.Length));
        }

        /// <summary>
        /// The basic operation in the Fischer-Yates shuffle.
        /// Swaps an element with a random one, but does not alter any 
        /// elements below the index of the one being shuffled.
        /// </summary>
        private void fischerYatesSwap(object[] array, int floor)
        {
            /*
            if (floor < 0) throw new ArgumentOutOfRangeException(
                "knuthSwap: parameter floor must be greater than zero");
             * Enable above if debugging */

            int target    = _prng.Next(floor, array.Length);
            object tmp    = array[floor];
            array[floor]  = array[target];
            array[target] = tmp;
        }

        /// <summary>
        /// An efficient, linear time shuffle of the given array.
        /// Destructively shuffles the array in place.
        /// </summary>
        /// <param name="array">The array to be shuffled.</param>
        public void shuffle(object[] array)
        {
            //Use a Fischer-Yates swap on each element in the array
            for (int i = 0; i < array.Length; i++)
                fischerYatesSwap(array, i);
        }

        /// <summary>
        /// Crosses over two permutations such that the result is also
        /// a permutation, where each index contains an element which 
        /// can be found at the same index as one of the parents.
        /// 
        /// Each element on the arrays must occur only once on that array.
        /// 
        /// Both arrays must be the same length.
        /// 
        /// Both arrays must contain exactly the same elements.
        /// 
        /// If these preconditions are not met, the behavior of this 
        /// method is undefined. It will probably throw an exception.
        /// </summary>
        /// <typeparam name="T">The type of element contained in the input arrays.</typeparam>
        /// <param name="array1">A permutation of elements identical to the ones in array2.</param>
        /// <param name="array2">A permutation of elements identical to the ones in array1.</param>
        /// <returns>A permutation of elements where each index has the same value as the same index on one of the parent arrays.</returns>
        public T[] crossPermutations<T>(T[] array1, T[] array2)
        {
            //Check if the two arrays are the same length. If they are not, 
            // the input does not meet preconditions and behavior is undefined.
            //Here, we throw an exception.
            if(array1.Length != array2.Length) throw new ArgumentException(
                "crossPermutations: given arrays must be the same length");

            #region Inverse array indexing

            //These provide the "inverse" operations to array indexing.
            //They are used to "look ahead" and write elements that have been
            // deduced to be neccessary at a certain location.

            //Maps elements in the first array to their indices.
            Dictionary<T,int> array1Indexes = new Dictionary<T,int>();

            //Maps elements in the second array to their indices.
            Dictionary<T,int> array2Indexes = new Dictionary<T,int>();

            #endregion

            #region Avoiding duplicaton

            //Keeps track of elements already written to the output.
            //Prevents duplication.
            HashSet<T> taboos = new HashSet<T>();

            //These are the array indexes that have already been visited
            bool[] traversed = new bool[array1.Length];

            #endregion

            #region Initialization

            //The array we will be returning to the caller
            T[] output = new T[array1.Length];
            
            //This loop initializes the dictionaries for
            //reverse indexing and the checklist on where we've
            //already written to on it.
            for (int i = 0; i < array1.Length; i++)
            {
                array1Indexes.Add(array1[i], i);
                array2Indexes.Add(array2[i], i);
                traversed[i] = false;
            }

            #endregion

            //For every index on our output array...
            for (int i = 0; i < output.Length; i++)
            {
                //If we have already visited this index, do nothing
                if (!traversed[i])
                {
                    //Otherwise...

                    #region Trivial cases

                    //Check if one of the elements has already been written
                    // to the output array.
                    //If this is true for both, something is wrong, and we throw an exception.
                    if (taboos.Contains(array1[i]) && taboos.Contains(array2[i]))
                    {
                        throw new ArgumentException(
                            "An array provided to crossPermutations has at least one duplicate element");
                    }
                    else if (taboos.Contains(array1[i]))
                    {
                        taboos.Add(array2[i]);
                        output[i] = array2[i];
                    }
                    else if (taboos.Contains(array2[i]))
                    {
                        taboos.Add(array1[i]);
                        output[i] = array1[i];
                    }

                    #endregion

                    #region Inner Look-Ahead Loop

                    else
                    {
                        //We use a coin-flip to choose which read head to use
                        bool readingArray1 = coinflip();

                        //We put our heads at the current location
                        int headLocation = i;

                        for (; ; )
                        {
                            //Fetch the element from the chosen read head
                            T currentElem = readingArray1 ? array1[headLocation] : array2[headLocation];

                            //If that element has been written elsewhere before, good, terminate the loop
                            if (taboos.Contains(currentElem)) break;

                            //Otherwise, write the element with our write head on the output track
                            output[headLocation] = currentElem;

                            //Note that we've written to this location and will not need to do anything to
                            // it in the outer loop.
                            traversed[headLocation] = true;

                            //Toggle which read head we are using
                            readingArray1 = !readingArray1;

                            //Use inverse indexing to find out where we will be looking ahead because we know we have to write
                            // there.
                            bool gotNextLocation = readingArray1 ? array2Indexes.TryGetValue(currentElem, out headLocation)
                                : array1Indexes.TryGetValue(currentElem, out headLocation);

                            //If inverse indexing failed, our preconditions did not hold. Fail with an exception.
                            if (!gotNextLocation)
                                throw new ArgumentException("Arrays provided to crossPermutations have different elements");

                            //Finally, note that we have already written the element to our output array and do not
                            // need to write that element again.
                            taboos.Add(currentElem);
                        }
                    }

                    #endregion
                }
            }
            return output;
        }

        #endregion

        #region Weighted Choice

        //If .NET 4.0, provide IEnumerable<Tuple<T,Double>> as a better alternative. This was written for .NET 3.5
        /// <summary>
        /// Returns a series of objects given in the wheel, with the likelihood of
        /// hitting each object determined by the weight array.
        /// Both inputs to this function must be finite.
        /// </summary>
        /// <typeparam name="T">The type of object stored in the wheel</typeparam>
        /// <param name="weights">The likelihood of each index of the wheel being selected.</param>
        /// <param name="wheel">The values to be yielded by the wheel.</param>
        /// <returns>An infinite stream of results from spinning the wheel.</returns>
        public IEnumerable<T> getRoulleteWheel<T>(IEnumerable<double> weights, IEnumerable<T> wheel)
        {
            //Ban negative and zero weights.
            if (weights.Any(x => x <= 0)) throw new ArgumentOutOfRangeException
                ("Unexpected negative or zero weight while constructing roulette wheel");
            else return unsafeGetRoulleteWheel(weights, wheel);
        }

        //Actual logic for the roulette wheel
        public IEnumerable<T> unsafeGetRoulleteWheel<T>(IEnumerable<double> weights, IEnumerable<T> wheel)
        {
            var _weights = weights.ToArray();
            var _wheel = wheel.ToArray();

            //If the amount of weights given differs from the amount of elements to select from, user probably did not intend this.
            if (_weights.Length > _wheel.Length) throw new ArgumentException(
                 "getRoulleteWheel: Every choice must have an associated weight and vice versa.");
            var summations = SummingScan(_weights);
            return from ballLanding in roulleteWheelSpinner(summations) select _wheel[ballLanding];
        }

        /// <summary>
        /// Variation of <see cref="getRoulleteWheel`1"/> which allows negative weights.
        /// </summary>
        /// <remarks>
        /// If <paramref="forgiveness"> is set to 0, it amounts to setting the lowest weight to 0.
        /// The implementation works with sums of weights. If there are two duplicate sums of weights, the wheel may behave badly.
        /// Therefore 0 is not an allowed value for forgiveness, so that the resulting wheel is well-behaved.
        /// </remarks>
        /// <param name="weights">The weights associated with each object.</param>
        /// <param name="forgiveness">The weight that will be given to the least weighted element and added to all others.</param>
        /// <param name="wheel">The elements for which the associated weights are provided.</param>
        /// <returns>An infinite stream of elements chosen by the roulette wheel roll.</returns>
        public IEnumerable<T> getRoulleteWheel<T>(IEnumerable<double> weights, double forgiveness, IEnumerable<T> wheel)
        {
            if (forgiveness <= 0) throw new ArgumentOutOfRangeException("Forgiveness must be positive non-zero number");
            var minWeight = weights.Min();
            var transWeights = weights.Select(x => x - minWeight + forgiveness);
            return unsafeGetRoulleteWheel(transWeights, wheel);
        }

        #endregion
    }
}
